from heapq import heappop, heappush
from typing import List
from sortedcontainers import SortedList
import heapq, sortedcontainers


class BusiestServers:
    # 找到处理最多请求的服务器: 模拟 + 有序集合 + 优先队列
    def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:
        available = SortedList(range(k))
        busy = []
        requests = [0] * k
        for i, (start, t) in enumerate(zip(arrival, load)):
            while busy and busy[0][0] <= start:
                available.add(busy[0][1])
                heappop(busy)
            if len(available) == 0:
                continue
            j = available.bisect_left(i % k)
            if j == len(available):
                j = 0
            id = available[j]
            requests[id] += 1
            heappush(busy, (start + t, id))
            available.remove(id)
        maxRequest = max(requests)
        return [i for i, req in enumerate(requests) if req == maxRequest]

    @staticmethod
    def mainDemo():
        k = 3
        arrival = [1, 2, 3, 4, 5]
        load = [1, 2, 1, 2]
        s = BusiestServers()
        ret = s.busiestServers(k, arrival, load)
        print(ret)

    @staticmethod
    def testDemo():
        print(range(5))
        print(list(range(5)))
        print([0] * 5)
        arrival = [1, 2, 3, 4, 5]
        load = [1, 2, 1, 2]
        print(zip(arrival, load))
        print(enumerate(zip(arrival, load)))
        # zip 的作用是 可以将两个数组拼成 元组
        for i, (start, t) in enumerate(zip(arrival, load)):
            print(i, (start, t))
        for i in arrival:
            print(i, end='\t')
        print()
        # enumerate 的 作用是, 遍历时可以获取元素序号
        for i, req in enumerate(arrival):
            print(i, req)
        temp = [3, 1, 5, 2, 7]
        # heapify 构造小顶堆, heappop 弹出堆顶 heappush 压入元素
        heapq.heapify(temp)
        print(temp)
        print(heapq.heappop(temp))
        print(temp)
        print(heapq.heappop(temp))
        print(temp)
        print(heapq.heappop(temp))
        print(temp)
        print(heapq.heappop(temp))
        print(temp)
        print(heapq.heappop(temp))
        print(temp)
        temp = [3, 1, 5, 2, 7]
        heapq.heappush(temp, 0)
        print(temp)
        heapq.heappush(temp, 8)
        print(temp)
        # 生成排序列表
        print(sortedcontainers.SortedList(temp))
        temp = [2]
        # 列表不为空,则循环
        while temp:
            print("hello")
            temp.clear()


if __name__ == '__main__':
    b = BusiestServers()
    b.testDemo()
